题面

解题思路

线段树

分析

用一条路左端点的编号表示它的编号，实际上所求即为：

设 $\large sum(i,j)=\sum_{k=i}^jv_i$

区间修改，貌似线段树可以维护，于是就考虑在已知一段区间答案的情况下，怎么合并

1、如何合并区间

考虑两个区间合并增加的信息的值即可

在左区间中的 $i$ 和右区间中的 $j$ 的 $sum(i,j)$ 会对答案产生贡献，贡献为：

跑个暴力的代码：

for(i=l;i<=mid;++i)
    for(j=mid+1;j<=r;++j)
        for(k=i;k<=j;++k)
            ans+=v[i];

真·暴力

不过可以发现 $\large \sum_{i=l}^{mid}v[i]$ 这一段，每次必对答案造成贡献，也就是说会贡献 $r-mid$ 次，那么我们可以对左边整个区间记录一个从右开始的前缀和，但是由于每次更新时乘上的都是 $r-mid$ 次，所以可以再对从右开始的前缀和记录一个总和 $sumR$，表示这一段区间内所有从右开始的前缀和的总和，即：

同理，可以用 $sumL$ 来维护一个区间左端前缀和的总和

但是 $sumL$ 和 $sumR$ 有应该如何维护？

以 $sumL$ 为例，仍然像上面那样考虑，合并之后会多出 $r-mid$ 段 $sum(i,mid)$ ，加入答案即可，因此我们还要维护一个 $sum$ 表示区间和

于是合并两个区间即可写成：

inline void Update(rint k,rint ls,rint rs) {//原有的值加上新增的贡献
    f[k]=f[ls]+f[rs]+sumR[ls]*len[rs]+len[ls]*sumL[rs],
    sumR[k]=sumR[rs]+sumR[ls]+sum[rs]*len[ls],
    sumL[k]=sumL[ls]+sumL[rs]+sum[ls]*len[rs],
    sum[k]=sum[ls]+sum[rs];
}

2、如何更新答案/下传标记

在一个区间加上一个值 $v$，其对答案产生贡献的形式是一定的，总是那个暴力的式子，于是我们可以预处理出区间 $+1$ 的情况，加 $v$ 修改时，直接乘以预处理值即可，预处理的过程可以理解为上述合并过程，不过长度和 $sumR$ 和 $sumL$ 都可以通过 $l$ 和 $r$ 体现出来，不需要开数组额外记录

初始化过程如下：

inline void Init(rint k,rint ls,rint rs) {
    len[k]=len[ls]+len[rs],//原本是不用记录len的，但是每次求len有点小长，就写成这样了
    frc[k]=frc[ls]+frc[rs]+len[rs]*len[ls]*(len[ls]+1)/2+len[ls]*len[rs]*(len[rs]+1)/2;
}//和上述合并区间是一致的
inline void built(rint k,rint l,rint r) {
    if(l==r) {len[k]=frc[k]=1;return;}
    rint mid=(l+r)>>1,ls=k<<1;
    built(ls,l,mid),built(ls|1,mid+1,r);
    Init(k,ls,ls|1);
}

3、查询

查询时和合并区间一致

warning

计算 $(R-L+1)\times(R-L)$ 时一定开 $long\ long$，如果你事先将 $R$ 减了 $1$，概率就应改为 $(R-L+1)\times(R-L+2)$

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define inf 0x7f7f7f7f
#define N 100003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
int n,T,L,R;
LL ans,res,Sum,v,d,len[N<<2],frc[N<<2],sum[N<<2];
LL f[N<<2],tag[N<<2],sumL[N<<2],sumR[N<<2];
inline int read() {
    rint s=0,p=1;
    rgt char c=getchar();
    while(!isdigit(c)) {if(c=='-') p=-1;c=getchar();}
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s*p;
}
inline char get() {
    rgt char c=getchar();
    while(c<'A'||c>'Z') c=getchar();
    return c;
}
inline void Init(rint k,rint ls,rint rs) {
    len[k]=len[ls]+len[rs],
    frc[k]=frc[ls]+frc[rs]+len[rs]*len[ls]*(len[ls]+1)/2+len[ls]*len[rs]*(len[rs]+1)/2;
}
inline void built(rint k,rint l,rint r) {
    if(l==r) {len[k]=frc[k]=1;return;}
    rint mid=(l+r)>>1,ls=k<<1;
    built(ls,l,mid),built(ls|1,mid+1,r);
    Init(k,ls,ls|1);
}
inline void push(rint k,rint l,rint r) {//下传标记
    f[k]+=frc[k]*tag[k],
    sum[k]+=tag[k]*len[k];
    sumL[k]+=tag[k]*len[k]*(len[k]+1)/2;
    sumR[k]+=tag[k]*len[k]*(len[k]+1)/2;
    if(l!=r) {
        rint ls=k<<1;
        tag[ls]+=tag[k],
        tag[ls|1]+=tag[k];
    }
    tag[k]=0;
}
inline void Update(rint k,rint ls,rint rs) {
    f[k]=f[ls]+f[rs]+sumR[ls]*len[rs]+len[ls]*sumL[rs],
    sumR[k]=sumR[rs]+sumR[ls]+sum[rs]*len[ls],
    sumL[k]=sumL[ls]+sumL[rs]+sum[ls]*len[rs],
    sum[k]=sum[ls]+sum[rs];
}
inline void Modify(rint k,rint l,rint r) {
    if(tag[k]) push(k,l,r);
    if(r<L||R<l) return;
    if(L<=l&&r<=R) {tag[k]=v;return push(k,l,r);}
    rint mid=(l+r)>>1,ls=k<<1;
    Modify(ls,l,mid),Modify(ls|1,mid+1,r);
    Update(k,ls,ls|1);
}
inline void Add(rint k,rint L) {
    ans+=f[k]+L*sumL[k]+Sum*len[k],
    Sum+=L*sum[k]+sumR[k];
}
inline void Query(rint k,rint l,rint r) {
    if(tag[k]) push(k,l,r);
    if(r<L||R<l) return;
    if(L<=l&&r<=R) return Add(k,l-L);//计算答案和合并区间已知
    rint mid=(l+r)>>1,ls=k<<1;
    Query(ls,l,mid),Query(ls|1,mid+1,r);
}
inline LL gcd(rgt LL a,rgt LL b) {
    return b?gcd(b,a%b):a;//处理gcd是也需要LL
}
int main()
{
    int i,op;
    n=read()-1,T=read(),built(1,1,n);
    while(T--) {
        op=get(),L=read(),R=read()-1,res=1ll*(R-L+1)*(R-L+2);
        if(op=='C') v=read(),Modify(1,1,n);
        else {
            ans=Sum=0;
            Query(1,1,n),ans*=2;
            d=gcd(ans,res);
            printf("%lld/%lld\n",ans/d,res/d);
        }
    }
    return 0;
}

devil.